﻿using System;

public class Exam
{
    public class MaterialData
    {
        public ItemData item;   //合成所需的物品
        public int count;       //合成所需的该物品的数量
    }

    public class ItemData
    {
        public int id;                          //物品 ID
        public int count;                       //当前拥有的物品数量
        public int costGold;                    //合成该物品所需的金币
        public List<MaterialData> materialList; //合成该物品所需的材料

        public ItemData(int _id,int _count,int _costgold, List<MaterialData> list)
        {
            id = _id;
            count = _count;
            costGold = _costgold;
            materialList = list;
        }
    }

    /// <summary>
    /// 计算用 totalGold 金币最多可以合成的 item 装备的数量
    /// </summary>
    /// <param name="item">要合成的装备</param>
    /// <param name="totalGold">拥有的金币</param>
    /// <returns>可合成的 item 装备的最大数量</returns> 
    public int Run(ItemData item, int totalGold)
    {
        int cnt = 0;
        return dfs(item, item, totalGold, ref cnt);
    }

    public int dfs(ItemData cur, ItemData item, int total, ref int cnt)
    {
        var list = cur.materialList;
        int sum = 0;
        int num = int.MaxValue;
        for (int i = 0; i < list.Count; i++)
        {
            sum += dfs(list[i].item, item, total, ref cnt);

            num = Math.Min(num,cnt / list[i].count);
        }

        sum += cur.costGold;
        if (num == int.MaxValue)
            num = 0;
        cnt = num + cur.count;
        if(cur == item)
        {
            sum = Math.Min(total / sum, cnt);
        }
        return sum;
    }
}


namespace Alpaca
{
    class Program
    {
        static void Main(string[] args)
        {
            Exam exam = new Exam();
            List<Exam.MaterialData> list = new List<Exam.MaterialData>();
            List<Exam.MaterialData> listA = new List<Exam.MaterialData>();
            List<Exam.MaterialData> listB = new List<Exam.MaterialData>();
            List<Exam.MaterialData> listD = new List<Exam.MaterialData>();

            Exam.ItemData itemC = new Exam.ItemData(3, 100, 0, list);
            Exam.ItemData itemE = new Exam.ItemData(5, 30, 0, list);
            Exam.ItemData itemF = new Exam.ItemData(6, 1500, 0, list);
            Exam.ItemData itemG = new Exam.ItemData(7, 3600, 0, list);

            listB.Add(new Exam.MaterialData() { item = itemE, count = 1 });
            listB.Add(new Exam.MaterialData() { item = itemF, count = 5 });

            listD.Add(new Exam.MaterialData() { item = itemG, count = 9 });

            Exam.ItemData itemB = new Exam.ItemData(2, 0, 53, listB);
            Exam.ItemData itemD = new Exam.ItemData(4, 0, 58, listD);

            listA.Add(new Exam.MaterialData() { item = itemB, count = 3 });
            listA.Add(new Exam.MaterialData() { item = itemC, count = 1 });
            listA.Add(new Exam.MaterialData() { item = itemD, count = 4 });

            Exam.ItemData itemA = new Exam.ItemData(1, 0, 26, listA);

            int res = exam.Run(itemA, 1370);

            Console.WriteLine(res);
        }
    }
}